package leetcode;
/**
 * 105.从前序与中序遍历序列构造二叉树
 * 给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 */
public class Num_105 {
    //前序遍历特点：第一个节点就是根节点
    //中序遍历特点：根节点的左边是左子树，右边是右子树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int size = preorder.length;
        if(size == 1){
            return new TreeNode(preorder[0]);
        }
        return subBuildTree(preorder, 0, size-1, inorder);
    }

    //preorder数组中遍历的索引
    private int indexRoot = 0;
    //构建区间集合中的二叉树,并返回根节点
    private TreeNode subBuildTree(int[] preorder, int headIndex, int tailIndex, int[] inorder) {
        //边界条件
        if(indexRoot >= preorder.length || headIndex > tailIndex){
            return null;
        }
        //先创建根节点
        int rootVal = preorder[indexRoot];
        indexRoot ++;
        TreeNode root = new TreeNode(rootVal);
        //找到根节点在inorder数组中的索引位置
        int rootIndexOf = rootIndexOfInorder(rootVal, inorder);

        //再创建左子树
        TreeNode left = subBuildTree(preorder, headIndex, rootIndexOf-1, inorder);

        //再创建右子树
        TreeNode right = subBuildTree(preorder, rootIndexOf+1, tailIndex, inorder);

        //最后连接二叉树
        root.left = left;
        root.right = right;

        return root;
    }

    //返回值为rootVal的元素下标位置
    private int rootIndexOfInorder(int rootVal, int[] inorder) {
        for(int i=0; i<inorder.length; i++){
            if(inorder[i] == rootVal){
                return i;
            }
        }
        return -1;
    }
}
